﻿#pragma once

#include<assert.h>
#include<iostream>
using namespace std;


template<class K, class V>
struct AVLTreeNode
{
	pair<K, V> _kv;//模版类
	AVLTreeNode<K, V>* _left;//左子节点
	AVLTreeNode<K, V>* _right;//右子节点
	AVLTreeNode<K, V>* _parent;//父节点
	int _bf;//平衡因子(balance factor)

	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{ }
};

template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;//跟节点父节点为空
		Node* cur = _root;//要插入节点从根部开始往下寻找插入节点

		//1.寻找插入位置
		while (cur)
		{
			if (cur->_kv.first < kv.first)//指向节点<插入节点,大靠右
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)//指向节点>插入节点,小靠左
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;//相等插入失败
			}
		}

		//2.插入
		cur = new Node(kv);//开辟新内存空间，存储值为kv
		//判断插入左子节点还是右子节点
		if (parent->_kv.first < kv.first)//父节点<插入节点，大靠右
		{
			parent->_right = cur;
		}
		else//小靠左
		{
			parent->_left = cur;
		}
		cur->_parent = parent;//更新父节点，子节点默认为空

		//3.更新平衡因子
		while (parent)//从当前插入节点往上(找父节点)更新
		{
			if (cur == parent->_left)//插入左节点，平衡因子--(平衡因子=右-左)
				parent->_bf--;
			else//插入右节点，平衡因子++
				parent->_bf++;

			if (parent->_bf == 0)//3.1平衡因子为0，停止更新
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)//3.2平衡因子为1或-1，继续向上更新
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf - 2)//3.3平衡因子为2或-2，旋转后停止更新
			{
				//旋转
				if (parent->_bf == 2 && cur->_bf == 1)//亲2子1，左旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)//亲2子-1，右左旋
				{
					RotateRL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)//亲-2子1，左右旋
				{
					RotateLR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)//亲-2子-1，右旋
				{
					RotateR(parent);
				}
				else
				{
					assert(false);
				}

				break;
			}
			else//3.4预防bug，以防出现平衡因子绝对值>3情况
			{
				assert(false);
			}
		}

		return true;
	}

	void RotateL(Node* parent)//左旋
	{
		//parent现亲，新左；subR现子，新亲；subRL现子左，新左右
		Node* subR = parent->_right;//子
		Node* subRL = subR->_left;//子左

		//不费口舌，看懂就行

		//现节点会变为新左节点，现右左节点会变为新左右节点，具体画图
		parent->_right = subRL;
		if (subRL)//若为空，则不必处理
		{
			subRL->_parent = parent;//处理[现右左节点会变为新左右节点]
		}
		Node* parentParent = parent->_parent;//因为接下来会改变现亲节点，记录下，后续用
		subR->_left = parent;//子左为现亲(现子后续变新亲)
		parent->_parent = subR;//现亲亲为现子(后续现亲变新亲左，现子变新亲)

		if (parentParent == nullptr)
		{//若现亲亲为空，说明现亲parent为根节点，后续要更新下根节点
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{//确认下现亲是现亲亲左右哪个节点,然后更新
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}

		//平衡因子更新,只有两个更新，parent(2->0)和subR(1->0)
		parent->_bf = subR->_bf = 0; 
	}

	void RotateR(Node* parent)//右旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		Node* parentParent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		if (parentParent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}

		parent->_bf = subL->_bf = 0;
	}

	void RotateLR(Node* parent)//左右双旋
	{
		//旋转后地址改变，不便寻找，旋转前记录旋转会改变平衡因子的节点，parent,subL,subLR，怎么找的，画图看
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;//经过观察，根据subLR的平衡因子，即可推断出旋转后3个节点平衡因子
		//计算公式，subLR->_bf恒为0
		//bf,subL->_bf,parent->_bf;0 0 0;1 -1 0;-1 0 1

		//先子左旋，后亲右旋,旋转容易，难的是更新旋转后的平衡因子
		RotateL(parent->_left);
		RotateR(parent);
		
		subLR->_bf = 0;
		if (bf == 0)
		{
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else if(bf == 1)
		{
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == -1)
		{
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else
		{
			assert(false);
		}
	}

	void RotateRL(Node* parent)//右左双旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		subRL->_bf = 0;
		if (bf == 0)
		{
			subR->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			subR->_bf = 1;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	Node* _root = nullptr;
};






